package com.cty._03_SolutionSeekingMindset._28_IsSymmetrical;

/**
 * @Auther: cty
 * @Date: 2020/7/10 11:52
 * @Description: 面试题28：对称的二叉树
 * 题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和
 * 它的镜像一样，那么它是对称的。
 * @version: 1.0
 */
public class IsSymmetrical {

    public static boolean isSymmetrical(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return false;

        return recIsSymmetrical(treeRoot, treeRoot);
    }  // end isSymmetrical()

    private static boolean recIsSymmetrical(BinaryTreeNode treeRoot1, BinaryTreeNode treeRoot2){
        if(treeRoot1==null && treeRoot2==null)  // 都为null
            return true;
        if(treeRoot1==null || treeRoot2==null)  // 两个中有一个为bull
            return false;
        if(treeRoot1.value != treeRoot2.value)  // 都不为null，但值不同
            return false;

        return recIsSymmetrical(treeRoot1.leftChild, treeRoot2.rightChild) && recIsSymmetrical(treeRoot1.rightChild, treeRoot2.leftChild);  // 都不为null，且值相同
    }  // end recIsSymmetrical()

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}

    public BinaryTreeNode(int value){this.value = value;}
}  // end class
